package god.day03;

/**
 * @author wang hao
 * @date 2023-02-19 00:31
 *
 *      小和问题
 *          每个位置的数 左边比自己小的数 累加   要求 N(logN) 时间复杂度
 */
public class Demo02 {

    // test(3)  val=>3  -> test(2) val=>2  -> test(1)   阶乘
    public static int test(int val){
        if (val < 1) return 1;
        return val *  test(val - 1);
    }

    public static void main(String[] args) {
        System.out.println(test(3));
    }



    // 小和问题
    public static int smallSum(int[] arr){
        if (arr == null || arr.length < 2){
            return 0;
        }
        return process(arr, 0, arr.length - 1);

    }

    private static int process(int[] arr, int L, int R) {
        if (L == R){
            return 0;
        }

        int mid = L + ((R -L) >> 1 );
        return process(arr, L, mid)
                +
                process(arr, mid + 1, R)
                +
                merge(arr, L, mid, R);

    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int help[] = new int[r - l + 1];
        int i = 0;
        int p1 = 0;
        int p2 = mid + 1;
        int res = 0;

        while (p1 <= mid && p2 <= r){
            res += arr[p1] < arr[p2] ? arr[p1] * (r - p2 + 1) : 0; // 左边 小于 右边 说明右边所有的数都比 目前的 p1 数大
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        while (p1 <= mid){
            help[i++] = arr[p1++];
        }

        while (p2 <= r){
            help[i++] = arr[p2++];
        }


        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
        return res;
    }

}
